package 数据结构专栏.简单级别;


import 数据结构专栏.B_链表专栏.ListNode;

/**
 * @DESC https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @Author tzq
 * @Date 2020-03-26 17:11
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 **/
public class _21_合并两个有序链表 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        print(listNode1);

        ListNode listNode21 = new ListNode(1);
        ListNode listNode22 = new ListNode(3);
        ListNode listNode23 = new ListNode(4);
        listNode21.next = listNode22;
        listNode22.next = listNode23;
        print(listNode21);

        print(mergeTwoLists(listNode1,listNode21));

//        1 2 4
//        1 3 4
//        1 1 2 3 4 4

    }

    /**
     * 1,1 -> 1
     * 1,3 -> 1
     * 2,3 -> 2
     * 4,3 -> 3
     * 4,4 -> 4
     * 4,N -> 4
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        //递归的第一步：终止条件，l1 == null,则返回l2. l2 == null,则返回l1
        if (l1 == null && l2 != null ) {
            return l2;
        }
        if (l2 == null && l1 != null ) {
            return l1;
        }
        if(l1 == null && l2 == null) {
            throw new RuntimeException("输入ListNode不能为NULL");
        }
        if (l1.val < l2.val) {
            //如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            //如果 l2 的 val 值更小，则将 l2.next 与排序好的链表头相接
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    private static void print(ListNode curr) {
        if (curr == null) {
            return;
        }
        if (curr.next != null) {
            System.out.print(curr.val + " ");

        } else {
            System.out.print(curr.val + "\n");
        }
        print(curr.next);

    }

}

